package dateStructure;

public class huffmanTree {
    private static int Maxbit = 107;
    private static int Maxvalue = Integer.MAX_VALUE;
    private static int Maxleaf = 35;
    private static int Maxnode = Maxleaf * 2 - 1;

    public static void main(String arg[]) {
        int n=6;
        TNode huffNode[] = new TNode[Maxnode];
        TCode huffCode[] = new TCode[Maxbit];
        huffNode = huffmancreateTree(huffNode, n);
        huffCode = huffmancreateCode(huffNode, huffCode, n);
        for (int i = 0; i < n; i++) {
            System.out.print("节点" + huffNode[i].value + "的哈夫曼编码为：");
            for (int j = huffCode[i].start + 1; j < n; j++) {
                System.out.print(huffCode[i].bit[j]);
            }
            System.out.println();
        }
    }

    private static class TNode {
        int lchild, rchild, parent;
        String value;
        double weight;
    }

    private static class TCode {
        int bit[]=new int[Maxbit];
        int start;
    }

    /**
     *
     * @param huffNode 代表树的每一个节点
     * @param n 节点个数
     * @return
     */
    private static TNode[] huffmancreateTree(TNode huffNode[], int n) {
        int x1, x2;
        double m1, m2;
        for (int i = 0; i < 2 * n - 1; i++) {
            huffNode[i] = new TNode();
            huffNode[i].lchild = -1;
            huffNode[i].rchild = -1;
            huffNode[i].parent = -1;
            huffNode[i].weight = 0;
        }
        huffNode[0].value = "a";
        huffNode[0].weight = 5;

        huffNode[1].value = "b";
        huffNode[1].weight = 32;

        huffNode[2].value = "c";
        huffNode[2].weight = 18;

        huffNode[3].value = "d";
        huffNode[3].weight = 7;

        huffNode[4].value = "e";
        huffNode[4].weight = 25;

        huffNode[5].value = "f";
        huffNode[5].weight = 13;

        huffNode[6].value = "";
        huffNode[6].weight = 0;

        huffNode[7].value = "";
        huffNode[7].weight = 0;

        huffNode[8].value = "";
        huffNode[8].weight = 0;

        huffNode[9].value = "";
        huffNode[9].weight = 0;

        huffNode[10].value = "";
        huffNode[10].weight = 0;

        for (int i = 0; i < n - 1; i++) {//n-1次合并
            m1 = m2 = Maxvalue;
            x1 = x2 = 0;
            for (int j = 0; j < n + i; j++) {
                if (huffNode[j].weight < m1 && huffNode[j].parent == -1) {
                    m2 = m1;
                    x2 = x1;
                    m1 = huffNode[j].weight;
                    x1 = j;
                } else if (huffNode[j].weight < m2 && huffNode[j].parent == -1) {
                    m2 = huffNode[j].weight;
                    x2 = j;
                }
            }
            huffNode[x1].parent = n + i;
            huffNode[x2].parent = n + i;
            huffNode[n + i].lchild = x1;
            huffNode[n + i].rchild = x2;
            huffNode[n + i].weight = m1 + m2;
            System.out.println("x1的权值：" + huffNode[x1].weight + "与x2的权值：" + huffNode[x2].weight + "-合在一起为：" + huffNode[n + i].weight);
        }
        return huffNode;
    }

    /**
     *
     * @param huffNode 哈夫曼节点
     * @param huffCode 哈夫曼代码
     * @param n 节点个数
     * @return
     */
    private static TCode[] huffmancreateCode(TNode huffNode[], TCode huffCode[], int n) {
//        TCode code = new TCode();
//        int p,c;
//        for (int i = 0; i < n; i++) {//计算每一个节点的哈夫曼编码
//            code.start = n - 1;
//            c=i;
//            p = huffNode[c].parent;
//            while (p != -1) {//可能循环多次 所以必须要设置一个变量c 不能单纯用i代替！
//                if (huffNode[p].lchild == c) {
//                    code.bit[code.start--] = 0;
//                } else {
//                    code.bit[code.start--] = 1;
//                }
//                c=p;
//                p = huffNode[c].parent;
//            }
//            //将临时找到的哈夫曼编码放到每个节点的哈夫曼编码集合中
//            huffCode[i] = new TCode();
//            for (int j = code.start + 1; j < n; j++) {
//                huffCode[i].bit[j] = code.bit[j];
//            }
//            huffCode[i].start = code.start;//最后将这个位置下标赋给节点
//        }
        //更简单做法！！！
        int c,p;
        for(int i=0;i<n;i++){
            huffCode[i]=new TCode();
            huffCode[i].start=n-1;
            c=i;
            p=huffNode[c].parent;
            while (p!=-1){
                if(huffNode[p].lchild==c){
                    huffCode[i].bit[huffCode[i].start--]=0;
                }
                else{
                    huffCode[i].bit[huffCode[i].start--]=1;
                }
                c=p;
                p=huffNode[c].parent;
            }
        }
        return huffCode;
//        return huffCode;
    }
}
